package com.bigshen.algorithm.eTwoPointer.solution03ValidTriangle;

import java.util.Arrays;

/**
 *
 * Given an array consists of non-negative integers, your task is to count the number of triplets chosen from the array that can make triangles if we take them as side lengths of a triangle.
 * Example 1:
 * Input: [2,2,3,4]
 * Output: 3
 * Explanation:
 * Valid combinations are:
 * 2,3,4 (using the first 2)
 * 2,3,4 (using the second 2)
 * 2,2,3
 *
 * Example 2:
 * Input: [1,2,3,4,5,6]
 * Output: 7
 *
 * Example 3:
 * Input: [24,3,82,22,35,84,19]
 * Output: 10
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/valid-triangle-number
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 *
 */
public class Solution {

    // 两边之和大于第三边， 第三边以最大值固定
    public int triangleNumber(int[] nums) {

        if (null == nums || nums.length < 3) {
            return 0;
        }

        Arrays.sort(nums);

        int total = 0;
        for (int i = nums.length - 1; i > 1; i--) {
            int start = 0;
            int end = i-1;
            while(start < end) {
                // 两边之和大于第三边
                if (nums[start] + nums[end] > nums[i]) {
                    // 正向排序，start开始满足，则后续也一定满足两边之和大于第三边
                    total += (end-start);
                    end--;
                } else {
                    start++;
                }
            }
        }
        return total;
    }

    public static void main(String[] args) {

        int[] array = {24,3,82,22,35,84,19};

        System.out.println(new Solution().triangleNumber(array));

    }

}
